#include <iostream>
using namespace std;

// 定义单链表节点结构体
struct ListNode {
    int val; // 存储节点数据
    ListNode* next; // 指向下一个节点的指针
};

// 初始化单链表
ListNode* initList() {
    ListNode* head = nullptr; // 初始化头节点为空
    ListNode* cur = nullptr; // 初始化当前节点为空

    int data;
    cout << "请输入数据(以-1 结束): ";
    cin >> data;

    while (data != -1) {
        ListNode* newNode = new ListNode(); // 创建新节点
        newNode->val = data; // 赋值节点数据
        newNode->next = nullptr; // 初始化下一个节点为空

        if (head == nullptr) { // 如果头节点为空，则将新节点作为头节点
            head = newNode;
        } else { // 否则，将新节点插入到链表尾部
            cur->next = newNode;
        }
        cur = newNode; // 将当前节点指向下一个节点

        cout << "请输入数据(以-1 结束): ";
        cin >> data;
    }

    return head;
}

// 打印单链表
void printList(ListNode* head) {
    ListNode* cur = head; // 初始化当前节点为头节点
    while (cur != nullptr) { // 当当前节点不为空时
        cout << cur->val << " "; // 输出当前节点数据
        cur = cur->next; // 将当前节点指向下一个节点
    }
    cout << endl; // 输出换行
}

// 分割链表
ListNode* split1(ListNode* head, int x) {
    ListNode* lessThanX = nullptr; // 小于 x 的链表头节点
    ListNode* greaterThanX = nullptr; // 大于等于 x 的链表头节点

    ListNode* cur = head; // 初始化当前节点为头节点
    ListNode* prev = nullptr; // 初始化前一个节点为空

    while (cur != nullptr) { // 当当前节点不为空时
        if (cur->val < x) { // 如果当前节点数据小于 x
            if (lessThanX == nullptr) { // 如果小于 x 的链表头节点为空
                lessThanX = cur; // 将当前节点作为小于 x 的链表头节点
            } else { // 否则
                prev->next = cur; // 将前一个节点的下一个节点指向当前节点
            }
            prev = cur; // 将前一个节点更新为当前节点
        } else { // 否则
            if (greaterThanX == nullptr) { // 如果大于等于 x 的链表头节点为空
                greaterThanX = cur; // 将当前节点作为大于等于 x 的链表头节点
            } else { // 否则
                prev->next = cur; // 将前一个节点的下一个节点指向当前节点
            }
        }
        cur = cur->next; // 将当前节点指向下一个节点
    }

    prev->next = nullptr; // 将最后一个小于 x 的节点的下一个节点设置为空

    return lessThanX; // 返回小于 x 的链表头节点
}

ListNode* split2(ListNode* head, int x) {
    ListNode* lessThanX = nullptr; // 小于 x 的链表头节点
    ListNode* greaterThanX = nullptr; // 大于等于 x 的链表头节点

    ListNode* cur = head; // 初始化当前节点为头节点
    ListNode* prev = nullptr; // 初始化前一个节点为空

    while (cur != nullptr) { // 当当前节点不为空时
        if (cur->val >= x) { // 如果当前节点数据大于等于 x
            if (greaterThanX == nullptr) { // 如果大于等于 x 的链表头节点为空
                greaterThanX = cur; // 将当前节点作为大于等于 x 的链表头节点
            } else { // 否则
                prev->next = cur; // 将前一个节点的下一个节点指向当前节点
            }
            prev = cur; // 将前一个节点更新为当前节点
        } else { // 否则
            if (lessThanX == nullptr) { // 如果小于 x 的链表头节点为空
                lessThanX = cur; // 将当前节点作为小于 x 的链表头节点
            } else { // 否则
                prev->next = cur; // 将前一个节点的下一个节点指向当前节点
            }
        }
        cur = cur->next; // 将当前节点指向下一个节点
    }

    prev->next = nullptr; // 将最后一个大于等于 x 的节点的下一个节点设置为空

    return lessThanX; // 返回小于 x 的链表头节点
}

int main() {
    ListNode* head = initList(); // 初始化单链表

    // 分割链表
    ListNode* lessThanX = split1(head, 5);
    ListNode* greaterThanX = split2(lessThanX, 5);

    // 打印小于 x 的链表
    printList(lessThanX);
    cout << endl;

    // 打印大于等于 x 的链表
    printList(greaterThanX);
    cout << endl;

    return 0;
}
